\documentclass[]{article} % list options between brackets
\usepackage{amsmath} % list packages between braces
\usepackage[utf8]{inputenc}
\usepackage{graphicx}
\usepackage{lmodern}

%Page
\addtolength{\oddsidemargin}{-.875in}
\addtolength{\evensidemargin}{-.875in}
\addtolength{\textwidth}{1.75in}
\addtolength{\topmargin}{-.875in}
\addtolength{\textheight}{1.75in}
%Page

% type user-defined commands here
\begin{document}

\title{Études et expérimentation de la reconnaissance des visage} % type title between braces
\author{NGUYEN Quoc Khai - Khong Minh Thanh} % type author(s) between braces
\date{29 Décembre, 2013} % type date between braces
\maketitle

\section{Introduction}
Dans le cadre de notre cours de reconnaissances de formes, il nous a été demandé
d’implémenter un système permettant de faire de la reconnaissance de visage. En effet, ce système peut reconnaître le visage à partir d'une image.

Afin de rendre compte du travail effectué dans ce projet, nous avons rédigé ce
rapport qui est structuré en quatre grandes parties:

- Descriptions les méthodes utilisées: KNN et FisherFace

- Présentation du programme

- Expérimentation

- Analyse des résultats obtenus afin de savoir les points forts et faible des méthodes utilisés

\section{Descriptions les méthodes utilisées}
Dans ce TP, nous avons utilisé 2 méthodes, K-plus proches voisins et FisherFace

\subsection{K-plus proches voisins Euclide}
Cette méthode est réalisé dans des étapes suivantes.
\subsubsection{Détection des blocks}
Chaque image est divisée en N blocks de même taille. On vous signale que le choix du nombre de block est si important, cela influence beaucoup au résultat de reconnaissance. Après avoir testé des paramètres, on a choisi de mettre $N = 14\times14 = 196$.
\subsubsection{Calcul du descripteur}
Un descripteur contient $N$ éléments et une valeur d'un élément $e$ est la somme des pixels d'un block qu'on a détecté dans la dernière étape.
\subsubsection{Calcul de la distance d'Euclide entre deux descripteurs}
\begin{equation}
D = \sqrt{\sum_{\substack{
(1<=i<=N)}} (e_{1i} - e_{2i})^2}
\end{equation}
\subsubsection{K-plus proches voisins (K1-Nearest Neighbors)} programme calcule la distance $D$ entre cette image avec toutes les images d'apprentissage, ils donnes $K$ . On choisi l'images ayant lesa distances lesa plus courtes. Choix du type le plus populaire pour le type de l'image de test. Ici, K est un paramètre d'entré. En observant le résultat des tests, nous tprouvons que $K = 4$ donne le meilleur résultat.
\subsection{Méthode FisherFace}
Le cœur de FisherFace est Linear Discriminant Analysis (LDA), qui maximise la différente entre les classes au lieu de maximiser la différente de tous les instances. L'idée de cette méthode est de chercher les des descripteurs qui permette de séparer les classes, mais ne pas séparer les instances dans une même classe. Cette méthode ressemble la méthode Principal Component Analysis (PCA) sauf qu'elle ne cherche pas tous les différentes entre les instances.
\subsubsection{Description de FisherFace}
En fait, dans OpenCV, il existe déjà l'implémentation de cette méthodes. Nous voulons présenter ici l'idée principale de la méthode. Pour avoir plus d'information, nous pouvons regarder l'article \cite{c1}, \cite{c2}

Soit X un vecteur aléatoire des échantillons tirés de classes de c:
\begin{align*}
X = \{X_1,X_2,\ldots,X_c\} \\
X_i = \{x_1, x_2, \ldots, x_n\}
\end{align*}

La dispersion des matrices $ S_ {B} $ et $ S_ {W} $ sont calculées comme:
\begin{align*}
S_{B} = \sum_{i=1}^{c} N_{i} (\mu_i - \mu)(\mu_i - \mu)^{T} \\
S_{W} = \sum_{i=1}^{c} \sum_{x_{j} \in X_{i}} (x_j - \mu_i)(x_j - \mu_i)^{T}
\end{align*}

où $\mu$ est la moyenne totale:

\begin{align*}
\mu = \frac{1}{N} \sum_{i=1}^{N} x_i
\end{align*}

%And $\mu_i$ is the mean of class $i \in \{1,\ldots,c\}$:
Et $\mu_i$ est la moyenne de la classe $i\in\{1,\ldots,c\}$:

\begin{align*}
\mu_i = \frac{1}{|X_i|} \sum_{x_j \in X_i} x_j
\end{align*}

%`Fisher’s classic algorithm now looks for a projection W, that maximizes the class separability criterion:
Algorithme de FisherFace cherche maintenant une projection W, qui maximise le critère de séparabilité des classes:

\begin{align*}
W_{opt} = \operatorname{arg\,max}_{W} \frac{|W^T S_B W|}{|W^T S_W W|}
\end{align*}

En fait, il existe déjà l'implémentation de cette méthodes dans OpenCV. Nous réutilisons simplement cette fonction.

\section{Présentation du programme}
\subsection{Pour la méthode KNN}
Ce programme contient 4 classes divisées en 8 fichiers : \textit{channel.h channel.cpp IO.h IO.cpp training.h training.cpp control.h et control.cpp} et un fichier de la fonction \textit{main}, \textit{main.cpp}. Un \textit{makefile} sert à faciliter de compiler le programme.

Ce programme a les fonctionnalités suivantes :
\begin{enumerate}
\item Création des descripteurs pour les images d'apprentissage ou de test et les enregistre dans un fichier.
\item A partir de deux fichiers de descripteur de test et d'apprentissage, le programme catégorise les images vers la catégorie correspondante.
\end{enumerate}

Dans ce programme, aucun algorithme est réutilisé. Par contre, nous avons utilisé la librairie OpenCV pour le traitement de base.
\subsection{Pour la méthode FisherFace}
Le programme FisherFace est déjà implémenté dans OpenCV (\cite{c2}), nous réutilisons simplement ce programme pour faire l'expérimentation.

L'utilisation du programme: \\
\textit{./recFisher csvTrain.ext csvTest.ext output\_folder}

Exemple: \\
\textit{./recFisher csvTest.ext csvTrain.ext result/}

Le ficher csvTrain.ext csvTest.ext contienne des lignes qui sont structurés comme:\\
\textit{filename; label}

Par exemple:\\
\textit{faces/s26/6.pgm;25\\
faces/s26/7.pgm;25\\
...\\
faces/s1/6.pgm;0\\
...}

\section{Expérimentation}
Pour faire l'expérimentation, nous avons utilisé les données de visage \textit{The ORL Data of faces} qui contient 40 visages, chaque visage est représenté par dix images. Nous avons divisé cette base en deux partie: 5 premières images pour l'apprentissage, et 5 dernières images pour le test.

\subsection{FisherFace}
En raison de la taille de matrice de confusion est trop grande ($40\times40$), nous présentons ici seulement le mauvais résultat.

\textbf{Résultat:}

Tout d'abord, nous regardons sur la taux de précision, ça veut dire que nous testons le programme avec les même base d'apprentissage et de test. Voici le résultat:\\
True : 200 False : 0\\
Rate : 100\%

On voit que le programme donne un résultat parfait. C'est parce que la méthode FisherFace peut chercher une bonne séparation entre les classes.

Nous regardons ensuite sur le résultat avec la base de test:\\
True : 163 false : 37\\
Rate : 81.5\%

On voit un taux de vrai est 81.5\%.

\subsection{Méthode KNN}
Avec cette méthode, pour obtenir le bon résultat, il faut bien choisir des paramètres
comme le nombre de block, le K plus proches voisins.\\
Nombre de block, ce paramètre est important. Quand le nombre de block est petit, le
résultat n'est pas exact. Par contre, quand on le met très grand, la méthode peut se
tromper aussi à cause des bruits dans les images.

\section{Analyse des résultats obtenus}
\subsection{Méthode FisherFace}
Ci-dessous sont des mauvais résultats de classification : \\
Actual class = 25 / Predicted class = \textbf{22}\\
Actual class = 32 / Predicted class = \textbf{22}\\
Actual class = 28 / Predicted class = \textbf{22}\\
...\\
Actual class = 19 / Predicted class = \textbf{22}\\
\textbf{Actual class = 15 / Predicted class = 0\\
Actual class = 15 / Predicted class = 0\\
Actual class = 15 / Predicted class = 0\\}
Actual class = 36 / Predicted class = \textbf{22}\\
...\\
\textbf{Actual class = 31 / Predicted class = 29\\
Actual class = 31 / Predicted class = 22\\
Actual class = 31 / Predicted class = 29\\
Actual class = 38 / Predicted class = 29\\
Actual class = 38 / Predicted class = 29\\}
...\\
\textbf{Actual class = 30 / Predicted class = 29\\
Actual class = 30 / Predicted class = 22\\
Actual class = 30 / Predicted class = 22\\}
Actual class = 18 / Predicted class = 28\\
\textbf{Actual class = 16 / Predicted class = 22\\
Actual class = 16 / Predicted class = 3\\
Actual class = 16 / Predicted class = 35\\}
Actual class = 35 / Predicted class = 0\\
Actual class = 35 / Predicted class = 39\\
\textbf{Actual class = 13 / Predicted class = 20\\
Actual class = 13 / Predicted class = 20\\
Actual class = 13 / Predicted class = 20\\
Actual class = 13 / Predicted class = 20\\
Actual class = 13 / Predicted class = 21\\}

On voit que dans le mauvais résultat, il y a des classes qui contienne beaucoup de mauvais classification, tel que: la classe 15, la classe 31, la classe 13. Les images dans ces classes sont classifiées dans certaines classes, par exemple: classe 22, classe 29, classe 20.

Pour comprendre mieux ce résultat, nous allons regarder les images de test qui ne sont pas bien classifiées :
\begin{figure}[!htb]
\minipage{0.15\textwidth}
\includegraphics[width=\linewidth]{faces/s14/6.jpg}
\caption{classe 13}
\endminipage\hfill
\minipage{0.15\textwidth}
\includegraphics[width=\linewidth]{faces/s14/7.jpg}
\caption{classe 13} %\label{fig:awesome_image3}
\endminipage\hfill
\minipage{0.15\textwidth}
\includegraphics[width=\linewidth]{faces/s14/8.jpg}
\caption{classe 13} %\label{fig:awesome_image3}
\endminipage\hfill
\minipage{0.15\textwidth}
\includegraphics[width=\linewidth]{faces/s14/9.jpg}
\caption{classe 13} %\label{fig:awesome_image3}
\endminipage\hfill

%\minipage{0.15\textwidth}
% \includegraphics[width=\linewidth]{faces/s14/1.jpg}
% \caption{classe 13}
%\endminipage\hfill
%\minipage{0.15\textwidth}
% \includegraphics[width=\linewidth]{faces/s14/2.jpg}
% \caption{classe 13} %\label{fig:awesome_image3}
%\endminipage\hfill
%\minipage{0.15\textwidth}
% \includegraphics[width=\linewidth]{faces/s14/3.jpg}
% \caption{classe 13} %\label{fig:awesome_image3}
%\endminipage\hfill
%\minipage{0.15\textwidth}
% \includegraphics[width=\linewidth]{faces/s14/4.jpg}
% \caption{classe 13} %\label{fig:awesome_image3}
%\endminipage\hfill
%\minipage{0.15\textwidth}
% \includegraphics[width=\linewidth]{faces/s14/5.jpg}
% \caption{classe 13} %\label{fig:awesome_image3}
%\endminipage\hfill

\minipage{0.15\textwidth}
\includegraphics[width=\linewidth]{faces/s21/1.jpg}
\caption{classe 20} %\label{fig:awesome_image3}
\endminipage\hfill
\minipage{0.15\textwidth}
\includegraphics[width=\linewidth]{faces/s21/2.jpg}
\caption{type 20} %\label{fig:awesome_image3}
\endminipage\hfill
\minipage{0.15\textwidth}
\includegraphics[width=\linewidth]{faces/s21/3.jpg}
\caption{type 24} %\label{fig:awesome_image3}
\endminipage\hfill
\minipage{0.15\textwidth}
\includegraphics[width=\linewidth]{faces/s21/4.jpg}
\caption{type 24} %\label{fig:awesome_image3}
\endminipage\hfill
\minipage{0.15\textwidth}
\includegraphics[width=\linewidth]{faces/s21/5.jpg}
\caption{type 24} %\label{fig:awesome_image3}
\endminipage\hfill
\end{figure}\\

Nous voyons que les deux types d'image sont un peu ressembles, le programme ne peut pas donc chercher les bonnes séparateurs pour la classe 13.
%
%\begin{figure}[!htb]
%\minipage{0.15\textwidth}
% \includegraphics[width=\linewidth]{faces/s23/1.jpg}
% \caption{classe 13}
%\endminipage\hfill
%\minipage{0.15\textwidth}
% \includegraphics[width=\linewidth]{faces/s23/2.jpg}
% \caption{classe 13} %\label{fig:awesome_image3}
%\endminipage\hfill
%\minipage{0.15\textwidth}
% \includegraphics[width=\linewidth]{faces/s23/3.jpg}
% \caption{classe 13} %\label{fig:awesome_image3}
%\endminipage\hfill
%\minipage{0.15\textwidth}
% \includegraphics[width=\linewidth]{faces/s23/4.jpg}
% \caption{classe 13} %\label{fig:awesome_image3}
%\endminipage\hfill
%\minipage{0.15\textwidth}
% \includegraphics[width=\linewidth]{faces/s23/5.jpg}
% \caption{classe 13} %\label{fig:awesome_image3}
%\endminipage\hfill
%\end{figure}\\



\subsection{Méthode KNN}
Tout d'abord, on observe le résultat de reconnaissance sur le taux de correct et le temps
\begin{figure}[!htb]
\minipage{0.55\textwidth}
\includegraphics[width=\linewidth]{images/g1.png}
\caption{Taux de correct}\label{fig:awesome_image2}
\endminipage\hfill
\minipage{0.55\textwidth}
\includegraphics[width=\linewidth]{images/g2.png}
\caption{Temps de calcul}\label{fig:awesome_image3}
\endminipage\hfill
\end{figure}\\
On trouve que quand le nombre de block est inférieur à 4, le taux de reconnaissance est très bas tandis que quand on beaucoup augmente le nombre de block, le temps de calcul va augmente aussi. Pour bien marcher, on mettre la nombre de block entre $8x8$ et $14x14$.\\
Par rapport cette graphique, on trouve le taux de correct de cette méthode est presque pareil pour deux façons de calcul la distance entre deux images. Par contre, pour le temps, la façon de calcul de la distance Cosine est un peu plus lent.\\
Le meilleur résultat est de 91,5\% avec la base donnée comme le consigne du TP, 5 premières images pour l'apprentissage et 5 dernières images pour le test. On trouve aussi quand on change le position la base de test et d'apprentissage, le résultat augmente jusqu'à 96,5\%\\
Dans l'implémentation, nous voulons lister seulement des images de reconnaissance faute.\\
Les reconnaissances fautes : Nous vous montrons ici quelques reconnaissances fautes
\begin{figure}[!htb]
\minipage{0.15\textwidth}
\includegraphics[width=\linewidth]{images/test1/2_24_8.png}
\caption{Image du type 2}\label{fig:awesome_image2}
\endminipage\hfill
\minipage{0.15\textwidth}
\includegraphics[width=\linewidth]{images/test1/6.png}
\caption{type 24}\label{fig:awesome_image3}
\endminipage\hfill
\minipage{0.15\textwidth}
\includegraphics[width=\linewidth]{images/test1/7.png}
\caption{type 24}\label{fig:awesome_image3}
\endminipage\hfill
\minipage{0.15\textwidth}
\includegraphics[width=\linewidth]{images/test1/8.png}
\caption{type 24}\label{fig:awesome_image3}
\endminipage\hfill
\minipage{0.15\textwidth}
\includegraphics[width=\linewidth]{images/test1/9.png}
\caption{type 24}\label{fig:awesome_image3}
\endminipage\hfill
\minipage{0.15\textwidth}
\includegraphics[width=\linewidth]{images/test1/10.png}
\caption{type 24}\label{fig:awesome_image3}
\endminipage\hfill
\end{figure}\\


\begin{figure}[!htb]
\minipage{0.15\textwidth}
\includegraphics[width=\linewidth]{images/test1/2/6.png}
\caption{type 2}\label{fig:awesome_image3}
\endminipage\hfill
\minipage{0.15\textwidth}
\includegraphics[width=\linewidth]{images/test1/2/7.png}
\caption{type 2}\label{fig:awesome_image3}
\endminipage\hfill
\minipage{0.15\textwidth}
\includegraphics[width=\linewidth]{images/test1/2/8.png}
\caption{type 2}\label{fig:awesome_image3}
\endminipage\hfill
\minipage{0.15\textwidth}
\includegraphics[width=\linewidth]{images/test1/2/9.png}
\caption{type 2}\label{fig:awesome_image3}
\endminipage\hfill
\minipage{0.15\textwidth}
\includegraphics[width=\linewidth]{images/test1/2/10.png}
\caption{type 2}\label{fig:awesome_image3}
\endminipage\hfill
\end{figure}

L'image de gauche est l'image de test et les autres sont les images d'apprentissage dans les quelques l'image de test est reconnue. La raison de reconnaissance faute est que si l'on ne compte que pixel par pixel, l'image de test n'est pas très différent les image d'apprentissage de ce type.

\subsection{Comparaison entre FisherFace et KNN}
Résultat :\\
Méthode FisherFace : taux de reconnaissance : 81.5\%, temps : 3.42s\\
Méthode NNC avec le nombre de block = 100 : taux de reconnaissance : 91.5\%, temps : 0.32s\\
Après voir testé les deux méthodes, on trouve que :\\
\begin{enumerate}
\item Méthode NNC est plus exact quand on bien choisi le nombre de block
\item Méthode NNC est plus vite
\end{enumerate}
\section{Conclusion}
Dans ce TP, nous avons utilisé deux méthodes de reconnaissance tels que : FisherFace et le plus proche voisin (NNC). Après avoir testé, on trouve que la méthode NNC est plus efficace si l'on bien choisit le nombre de block.

\clearpage
\begin{thebibliography}{9}
\bibitem{c1}
~Peter N. Belhumeur, Joao P. Hespanha, and David J. Kriegman
\emph{Eigenfaces vs. Fisherfaces: Recognition Using Class Specific Linear Projection}.
IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 19, NO. 7, JULY 1997

\bibitem{c2}
\emph{http:\/\/docs.opencv.org\/modules\/contrib\/doc\/facerec\/facerec\_tutorial.html\#id16}

\end{thebibliography}

\end{document}